package com.zwxu.tree;

import java.util.Stack;

public class ValidateBinarySearchTreeDemo {
	private static Stack<Integer> stack;
	 
	public static void main(String[] args) {
		TreeNode root = new TreeNode(2);
		TreeNode left = new TreeNode(1);
		TreeNode right = new TreeNode(4);
		TreeNode lright = new TreeNode(3);
		TreeNode rright = new TreeNode(5);
		root.left = left;
		right.left = lright;
		right.right = rright;
		root.right = right;
		// inOrder(root);
		System.out.print(isValidBST(root));

	}

	public static boolean isValidBST(TreeNode root) {
		if (root == null) {
			return true;
		}

		stack = new Stack<Integer>();
		inOrder(root);

		int i = stack.pop();
		int j;
		while (!stack.isEmpty()) {
			j = stack.pop();
			if (i <= j) {
				return false;
			}

			i = j;
		}

		return true;
	}

	public static void inOrder(TreeNode root) {
		if (root != null) {
			inOrder(root.left);
			//print(subTree);
			stack.push(root.val);
			inOrder(root.right);
		}
	}

	private static void print(TreeNode subTree) {
		System.out.print(subTree.val + ">>");

	}

}

class TreeNode {
	public int val;
	public TreeNode left, right;

	public TreeNode(int val) {
		this.val = val;
		this.left = this.right = null;
	}

}
